NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part2/12991

Internet Message Format | 1996-08-05 | 2.7 KB

Path: anvil.ugrad.cs.ubc.ca!not-for-mail
From: [e-mail] (Kazimir Kylheku)
Newsgroups: comp.arch.embedded,comp.lang.c
Subject: Re: Using malloc of C on embedded system?
Date: 3 Apr 1996 13:00:25 -0800
Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
Message-ID: <[e-mail]>
References: <4jml7h$[e-mail]> <4jrndq$[e-mail]> <4jtbot$[e-mail]>
NNTP-Posting-Host: anvil.ugrad.cs.ubc.ca

In article <4jtbot$[e-mail]>, John Payson <[e-mail]> wrote:
 >In article <4jrndq$[e-mail]>,
 >Risto Jokinen  <[e-mail]> wrote:
 >>This mechanism works. random size malloc/free does not work on embedded systems, or
 >>at least it is impossible to debug, and can be VERY slow. fixed size partition pool
 >>manager takes <<50us for malloc/free in any processor.
 >
 >Fixed-size malloc/free is often a good approach if it works; to help it
 >along, however, it's often useful to have a "version" of malloc for odd-
 >sized blocks that will never be freed (allocate a large memory pool for
 >these things and just track the last byte used), and sometimes useful to
 >have several memory pools for different-sized objects.
 >
 >As I mentioned in another post, the "binary buddy" system is often a good
 >compromise between internal and external fragmentation in embedded systems.

Also the fibonacci buddy system is also interesting. Whereas the binary buddy
system is based on the recurrence t[n] = 2t[n-1], t[0] = 1, fibonacci is based
on, of course, t[n] = t[n-1] + t[n-2], with t[0] = t[1] = 1.

Fibonacci will break the root cluster into two fibonacci numbers (the one which
precede N in the fibonacci sequence). If the starting chunk is size 13, and 2
units are requested, it will be broken into 8 and 5.  The smaller one will be
recursively checked, and broken into 2 and 3. The size 2 chunk will then be
assigned. If another request for size 2 is made, the 3 will be broken into 1
and 2.

 >The system is somewhat confusing to describe, but it offers lg(N) performance
 >without too much code or--if power-of-two memory sizes work well for your
 >application--memory overhead.  It also tends to produce minimal fragmentation:
 >while isolated unallocated spaces may get formed when non-consecutive blocks
 >are freed, such spaces will have effective priority when allocating new blocks.

I would also consider  a system that has a means to do heap compaction. It's
probably the only sure way to assure that the worst case fragmentation cannot
happen. This introduces quite a bit of complexity, but may be worthwhile when
memory is scarce. Plus one can always have escape hatches, such as the ability
to nail an allocated chunk in place so that it can't be moved by the compactor.

--